package Algoritmos;

import grafoS.Graph;

/**
 * Gcol is a program to help users to learn a little about graph coloring, in
 * this software, you can learn some coloring algorithms, and add your own
 * algorithm for coloring.You can also learn BFS and DFS search. This tool, also
 * support the .col format from DIMACS (Center for Discrete Mathematics and
 * Theoretical Computer Science), so you can import a big graph and use all the
 * algorithms. Copyright (C) <2015> Clóvis Daniel Souza Silva, Samuel Silva de
 * Souza, Professor Leonardo Sampaio Rocha.
 * 
* This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 * 
* This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 * 
* You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 * 
 * contact: projetoGrafos@gmail.com
 */

/**
 * 
 * @author Daniel.
 * @author Samuel.
 */

/**
 * 
 * In this class, we'll do the coloring in the graph, but following a DFS visit
 * order, it's important to say that we'll coloring just the connected vertices.
 * The colors will be integers 1 or above.
 * Any vertex not owned to the subgraph of the selected vertex will be filled
 * with -1 as it color.
 */
public class ColorirDfs extends Algorithm {
    Graph gr;
    int cor[];
    int matriz[][];
    
    /**
     * The ReturnColor is a virtual method from the class Algorithm.
     * @param g A graph, where we'll use the adjacency matrix.
     * @param vertice A integer, to represent the index of the vertex.
     * @return a vector with the size of the total of vertex, indicating
     * the color of each vertex
     */
    public int[] ReturnColor(Graph g, int vertice) {
        gr = g;
        matriz = g.getGrafo();
        cor = new int[g.getN()];
        int[] pilha = new int[g.getN()];
        DFS(pilha, vertice);
        for (int i = 0; i < pilha.length; i++) {
            
            if (pilha[i] != 0) {
                colorirBySteps(pilha[i] - 1);
            }
        }
        for(int i = 0; i< cor.length; i++)
        {
            pilha = new int[g.getN()];
            if(cor[i] == 0)
            {
                cor[i] = -1;
            }
               
        }
    return cor;
    

    }
    /**
     * coloringBySteps work coloring the vector cor by index.
     * 
     * @param v The index of the vertex to coloring.
     */
    public void colorirBySteps(int v) {
        int[][] Grafo = matriz;
        int[] adjacentes = new int[gr.getN()];
        for (int i = 0; i < adjacentes.length; i++) {
            if (Grafo[v][i] == 1) {
                if (cor[v] == cor[i] && cor[v] != 0) {
                    cor[v]++;
                    i = -1;
                }
                if (cor[v] == 0) {
                    cor[v]++;
                    i = -1;
                }
            }

        }
        if (cor[v] == 0)
            cor[v]++;

    }
    /**
     * This method will fill a stack to be used later for coloring.
     * @param p a vector to be used like a stack.
     * @param v the index of initial vertex.
     */
    public void DFS(int[] p, int v) {

        int topo = 0;
        int aux = topo;
        int[][] grafo = matriz;

        for (int i = v; i < gr.getN(); i++) {
            for (int j = 0; j <gr.getN(); j++) {
                if (grafo[i][j] >= 1 && checkVector(p, i + 1) == false) {
                    p[topo] = i + 1;
                    topo++;
                    aux++;
                    i = j;
                    j = -1;
                }
                if (p.length == topo) {
                    break;
                }
            }
        }
        if (vetorEstaNulo(p)) {
            p[0] = v + 1;
        }
    }
    /**
     * @see Graph
     * @return True ig the int is int the vector.
     */
    public boolean checkVector(int[] p, int a) {
        for (int i = 0; i < p.length; i++) {
            if (p[i] == a) {
                return true;
            }
        }
        return false;
    }
    /**
     * Checks if the vector is empty.
     * @param p the vector to be checked.
     * @return true if it's empty.
     */
     public boolean vetorEstaNulo(int[] p) {
        for (int i = 0; i < p.length; i++) {
            if (p[i] != 0) {
                return false;
            }
        }
        return true;
    }

}

